/*
 * @lc app=leetcode.cn id=23 lang=javascript
 *
 * [23] 合并K个升序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    let mergeToList=function(list1,list2){
        if(!list1)return list2
        if(!list2)return list1
        if(list1.val<list2.val){
           list1.next=mergeToList(list1.next,list2) 
           return list1
        }else{
            list2.next=mergeToList(list1,list2.next)
            return list2
        }
    }
    if(lists.length===0)return null
    let res=new ListNode(-Infinity)
    for(let i=0;i<lists.length;i++){
        res=mergeToList(res,lists[i])
    }
    return res.next
};
// @lc code=end

var mergeKLists = function(lists) {
    if (!lists.length) return null
    //递归出口，即数组中只剩一条链表时，合并完毕
    if (lists.length === 1) return lists[0]
    
    //两个一组的合并，合并完了更新数组（每次合并前两个）
    lists.splice(0, 2, mergeTwoLists(lists[0], lists[1]))
    //递归
    return mergeKLists(lists)
};//很棒的分治算法